package 动态规划;

public class 不同路径 {
    class Solution{
        public  int uniquePaths(int m,int n){
            //定义dp的意义 dp[i][j]就是到达（i，j）有多少条路径
             int[][] dp = new int[m][n];
             //初始化dp
            for (int i = 0; i < m; i++) {
                //j是0的话 从(0,0)到(i,0)的路径就是只有一条
                dp[i][0] = 1;
            }
            for (int j = 0; j < n; j++) {
                dp[0][j] = 1;
            }
            //推出递推公式是dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }
}
